// https://leetcode.cn/problems/design-skiplist/

// 跳表实现总结：
// 1. 使用多级链表结构实现O(logN)的搜索、插入、删除操作
// 2. 通过随机层数控制跳表平衡性，避免退化
// 3. 维护头节点作为搜索起点，动态调整层数
// 4. 插入时找到每层前驱节点，随机确定新节点层数
// 5. 删除时更新前后链接，清理空层优化空间

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include <ctime>
#include <cstdlib>

struct SkiplistNode
{
    int _val;
    vector<SkiplistNode *> _nextV;

    SkiplistNode(int val, int level)
        : _val(val), _nextV(level, nullptr)
    {
    }
};

class Skiplist
{
    typedef SkiplistNode Node;

public:
    Skiplist()
    {
        srand((unsigned)time(NULL));
        // 头节点，初始层数是1
        _head = new SkiplistNode(-1, 1);
    }

    // 搜索目标值是否存在
    bool search(int target)
    {
        Node* cur = _head;
        int level = _head->_nextV.size() - 1;

        while (level >= 0)
        {
            // 目标值比下一个节点值(存在)要大，向右走
            if (cur->_nextV[level] != nullptr && cur->_nextV[level]->_val < target)
            {
                // 向右走
                cur = cur->_nextV[level];
            }
            // 下一个节点是空(尾)，或者目标值比下一个节点值要小，向下走
            else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
            {
                // 向下走
                --level;
            }
            else
            {
                // 找到目标值
                return true;
            }
        }
        return false;
    }

    // 核心辅助函数：找到目标值在每一层的前驱节点
    std::vector<Node *> FindPrevNode(int num)
    {
        Node *cur = _head;
        int level = _head->_nextV.size() - 1;

        // 插入位置每一层前一个节点指针，初始化为头节点
        std::vector<Node *> prevv(level + 1, _head);

        while (level >= 0)
        {
            // 目标值比下一个节点值要大，向右走
            if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
            {
                // 向右走
                cur = cur->_nextV[level];
            }
            // 下一个节点是空(尾)，或者目标值比下一个节点值要小，向下走
            else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num)
            {
                // 更新level层的前驱节点
                prevv[level] = cur;
                // 向下走
                --level;
            }
        }
        return prevv;
    }

    // 插入数值
    void add(int num)
    {
        std::vector<Node *> prevv = FindPrevNode(num);

        int n = RandomLevel();
        Node *newnode = new Node(num, n);

        // 如果新节点的层数超过当前最大的层数，升高头节点的层数
        if (n > _head->_nextV.size())
        {
            _head->_nextV.resize(n, nullptr);
            prevv.resize(n, _head);
        }

        // 链接前后节点
        for (int i = 0; i < n; ++i)
        {
            newnode->_nextV[i] = prevv[i]->_nextV[i];
            prevv[i]->_nextV[i] = newnode;
        }
    }

    // 删除数值
    bool erase(int num)
    {
        vector<Node *> prevv = FindPrevNode(num);

        // 第一层下一个为空，或者值不匹配，说明val不在表中
        if (prevv[0]->_nextV[0] == nullptr || prevv[0]->_nextV[0]->_val != num)
        {
            return false;
        }
        else
        {
            Node *del = prevv[0]->_nextV[0];

            // 将del节点每一层的前后指针链接起来，跳过del节点
            for (size_t i = 0; i < del->_nextV.size(); i++)
            {
                prevv[i]->_nextV[i] = del->_nextV[i];
            }
            delete del;

            // 如果删除最高层节点，把头节点的层数也降一下
            int i = _head->_nextV.size() - 1;
            while (i >= 0)
            {
                if (_head->_nextV[i] == nullptr)
                    --i;
                else
                    break;
            }
            _head->_nextV.resize(i + 1);

            return true;
        }
    }
private:
    // 随机生成节点层数
    int RandomLevel()
    {
        size_t level = 1;
        // rand() -> [0, RAND_MAX]之间
        while (rand() <= RAND_MAX * _p && level < _maxLevel)
        {
            ++level;
        }
        return level;
    }
public:
    // 打印跳表结构（调试用）
    void Print()
    {
        int level = _head->_nextV.size();
        for (int i = level - 1; i >= 0; --i)
        {
            Node *cur = _head;
            std::cout << "Level " << i << ": ";
            while (cur)
            {
                if (cur == _head)
                {
                    std::cout << "HEAD";
                }
                else
                {
                    std::cout << cur->_val;
                }
                if (cur->_nextV[i])
                {
                    std::cout << " -> ";
                }
                cur = cur->_nextV[i];
            }
            std::cout << std::endl;
        }
    }

private:
    Node *_head;           // 头节点
    size_t _maxLevel = 32; // 最大层数限制
    double _p = 0.25;      // 节点增加一层的概率
};

int main()
{
    Skiplist *skiplist = new Skiplist();

    skiplist->add(1);
    skiplist->add(2);
    skiplist->add(3);
    cout << (skiplist->search(0) == 1 ? "True" : "False") << endl; // 返回 false
    skiplist->add(4);
    cout << (skiplist->search(1) == 1 ? "True" : "False") << endl; // 返回 true
    cout << (skiplist->erase(0) == 1 ? "True" : "False") << endl;  // 返回 false，0 不在跳表中
    cout << (skiplist->erase(1) == 1 ? "True" : "False") << endl;  // 返回 true
    cout << (skiplist->search(1) == 1 ? "True" : "False") << endl; // 返回 false，1 已被擦除

    skiplist->Print();

    return 0;
}